@InProceedings{10.1007/BFb0054380,
author="Sen, Sandeep
and Gupta, Neelima",
editor="Arnborg, Stefan
and Ivansson, Lars",
title="Distribution-sensitive algorithms",
booktitle="Algorithm Theory --- SWAT'98",
year="1998",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="335--346",
abstract="We investigate a new paradigm of algorithm design for geometric problems that can be termed distribution-sensitive. Our notion of distribution is more combinatorial in nature than spatial. We illustrate this on problems like planar-hulls and 2D-maxima where some of the previously known output-sensitive algorithms are recast in this setting. In a number of cases, the distribution-sensitive analysis yields superior results for the above problems. Moreover these bounds are shown to be tight for a certain class of algorithms.",
isbn="978-3-540-69106-8"
}